#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

string SEP = ",";     // 分隔符
string Null = "#";    // 空指针

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class TreeToString {
public:

    void stringBuilder(TreeNode *root, string &res) {
        if (root == nullptr) {
            res += Null;
            res += SEP;
            return;
        }
        // preorder
        res += to_string(root->val);
        res += SEP;
        stringBuilder(root->left, res);
        stringBuilder(root->right, res);
        /*
        // postorder
        stringBuilder(root->left, res);
        stringBuilder(root->right, res);
        res += to_string(root->val);
        res += SEP;
        */
    }

    void split(string &s, queue<string> &nodes, const string &token) {
        int length = s.size();
        int start = 0;
        int end = s.find(token);
        
        while (end != string::npos) {
            nodes.push(s.substr(start, end - start));
            start = end + token.size();
            end = s.find(token, start);
        }
        if (start != length)
            nodes.push(s.substr(start));
    }

    string serialize(TreeNode *root) {
        if (root == nullptr)
            return "";
        string res;
        stringBuilder(root, res);
        return res;
    }

    TreeNode *getDeserializedTree(queue<string> &nodes) {
        if (nodes.empty())
            return nullptr;
        
        string value = nodes.front();
        nodes.pop();

        if (value == Null)
            return nullptr;

        TreeNode *root = new TreeNode(stoi(value));
        root->left = getDeserializedTree(nodes);
        root->right = getDeserializedTree(nodes);
        /*
        // 先右后左，后序遍历需要使用stack记录数据
        TreeNode *root = new TreeNode(stoi(value));
        root->right = getDeserializedTree(nodes);
        root->left = getDeserializedTree(nodes);
        */
        return root;
    }

    TreeNode *deserialize(string data) {
        queue<string> nodes;
        split(data, nodes, SEP);
        return getDeserializedTree(nodes);
    }

    string serializeLevel(TreeNode *root) {
        if (root == nullptr)
            return "";
        queue<TreeNode *> q;
        q.push(root);
        string res;

        while (!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            if (cur == nullptr) {
                res += Null;
                res += SEP;
                continue;
            }
            res += to_string(cur->val);
            res += SEP;

            q.push(cur->left);
            q.push(cur->right);
        }
        return res;
    }

    TreeNode *deserializeLevel(string data) {
        if (data == "")
            return nullptr;
        queue<string> nodes;
        split(data, nodes, SEP);
        TreeNode *root = new TreeNode(stoi(nodes.front()));
        nodes.pop();
        queue<TreeNode *> q;
        TreeNode *parent;
        q.push(root); 

        while (!nodes.empty()) {
            parent = q.front();
            q.pop();

            string left = nodes.front();
            nodes.pop();
            if (left == Null)
                parent->left = nullptr;
            else {
                parent->left = new TreeNode(stoi(left));
                q.push(parent->left);
            }

            string right = nodes.front();
            nodes.pop();
            if (right == Null)
                parent->right = nullptr;
            else {
                parent->right = new TreeNode(stoi(right));
                q.push(parent->right);
            }
        }
        return root;
    }

};